Solving 10385 - Duathlon (Ternary search)
[andmenj-acm.git] / 11394 - Digit Blocks / robado.cpp
blob8e5cee452aed1393a041744bee922824ce789f48
1 //Este código produce TLE
2 //Robado de http://online-judge.uva.es/board/viewtopic.php?t=27307&start=15
3 //By arsalan_mousavian
5 #include <iostream>
6 #include <algorithm>
7 #include <memory>
8 #include <vector>
9 #include <cstdio>
10 #include <utility>
11 #include <fstream>
12 #include <string>
14 using namespace std;
15 #define ll long long
16 ll dp [1<<16][5] ;
17 char input [20];
19 inline int value ( char ch){
20 if ( isalpha ( ch ) ) return 10 + ch - 'A';
21 return ch - '0';
24 int main (){
25 while ( cin >> input ){
26 if ( !strcmp ( input , "#") ) break ;
28 int n = strlen ( input ) ;
29 sort ( input , input + n ) ;
30 for (register int mask = 0 ; mask < (1<<n) ; mask ++ ){
31 for ( int mod = 0 ; mod < 5 ; mod ++ ){
32 if ( mask == 0 ) dp [mask][mod] = 0 ;
33 else{
34 dp [mask][mod] = 0 ;
35 int prev = -1 ;
36 for ( int i=0 ; i<n ; i++ ){
37 if ( mask & ( 1<<i ) ){
38 int next = 0 ;
39 int cur = value ( input [i] );
40 if ( prev == cur ) continue ;
41 prev = cur ;
42 next = ( 500 + mod - cur ) % 5;
43 if ( next == 0 ) dp [mask][mod] ++ ;
44 dp[mask][mod] += dp[mask - (1<<i)][next];
48 if ( mask == (1<<n) - 1 && mod == 0 )
49 break ;
52 cout << dp [(1<<n)-1][0] << endl;